package com.coder.algorithm.sort;

/**
 * 插入排序
 * <p>
 * 将 0～i-1 位设置为有序，将后面的数据逐个插入到有序数列中
 *
 * @author yuhushuan
 * @date 2020/6/6 22:08
 */
public class InsertionSort implements Sort {

    public InsertionSort() {
        System.out.println("插入排序");
    }

    @Override
    public void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        // 第0位独自作为有序数列，从第1位开始向后遍历
        for (int i = 1; i < array.length; i++) {
            //0~i-1 位为有序，若第 i 位小于 i-1 位，继续寻位并插入，否则认为 0~i 位也是有序的，忽略此次循环，相当于continue
            if (array[i] < array[i - 1]) {
                // 保存第i位的值
                int temp = array[i];

                int j = i - 1;
                //从第 i-1 位向前遍历并移位，直至找到小于第i位值停止
                while (j >= 0 && temp < array[j]) {
                    array[j + 1] = array[j];
                    j--;
                }
                // 插入第 i 位的值
                array[j + 1] = temp;
            }
        }
    }
}
